class Solution {
public:
    int kIncreasing(vector<int>& arr, int k) {
        int n = arr.size(), ans = 0, size = 0;
        vector<int> nums;
        for (int i = 0; i < k; i++)
        {
            nums.clear();
            for (int j = i; j < n; j += k)
            {
                nums.push_back(arr[j]);
            }
            int len = lengthOfLIS(nums);
            ans += nums.size() - len;
        }
        return ans;
    }

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> ends(n, 0);
        int len = 0;
        for (int i = 0, find; i < n; i++)
        {
            find = check(ends, len, nums[i]);
            if (find == -1)
                ends[len++] = nums[i];
            else
                ends[find] = nums[i];
        }
        return len;
    }

    int check(vector<int>& ends, int len, int k)
    {
        int l = 0, r = len - 1;
        int ans = -1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (ends[mid] > k)
            {
                ans = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        return ans;
    }
};